package leetcode.linkedlist;

/**
 * 148. 排序链表
 *
 * 要求时间复杂度是 O(nlog n), 空间复杂度为 O(1)
 */
public class SortList {

    public static void main(String[] args) {
        SortList solution = new SortList();

        Integer[] arr1 = {4, 2, 1, 3};
        ListNode head = ListNode.makeLinkedList(arr1);

        ListNode newList = solution.sortList2(head);
        System.out.println(newList.list());
    }

    /**
     * 自顶向下归并排序
     *
     * 时间复杂度 O(nlogn), 空间复杂度 O(logn)
     *
     * @param head  链表的头节点
     * @return
     */
    public ListNode sortList(ListNode head) {
        // 当前链表只有一个节点的时候, 直接返回该节点, 这是递归中止的条件
        if (head == null || head.next == null)
            return head;
        // 使用快慢指针找到链表的中间节点
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 中间节点的下一个节点, 也就是分成两部分的第二个链表的开始节点
        ListNode mid = slow.next;
        // 断开链表
        slow.next = null;
        // 递归调用分割的两个链表, 得到排序后的链表
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        // 将两个排序链表合并, 转化为一个排序链表
        // 使用两个新的指针用于构建新链表, 一个保存头节点, 一个用于遍历
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }

    /**
     * 自底向上归并排序
     *
     * 时间复杂度 O(nlogn), 空间复杂度 O(1)
     *
     * @param head
     * @return
     */
    public ListNode sortList2(ListNode head) {
        if (head == null) {
            return head;
        }

        // 遍历得到链表的长度
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }

        // 头指针, 引入哑节点
        ListNode dummyHead = new ListNode(0, head);
        // 每次将链表拆分成若干个长度为 subLen的子链表, 并按照每两个子链表一组进行合并
        // 下一轮合并的时候, 子链表长度*2
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            // curr是遍历指针, 用于记录拆分链表的位置
            ListNode prev = dummyHead, curr = dummyHead.next;
            while (curr != null) {
                ListNode head1 = curr;
                // curr指针遍历到中间节点
                // 拆分出长度为subLen的链表1, head1指向第一个链表的头
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                // head2指向中间节点下一个位置, 也就是每组需要合并的第二条链表的头
                ListNode head2 = curr.next;
                // 断开第1个链表和第2个链表的链接
                curr.next = null;
                // curr指针遍历到每组链表的结尾(合并的第二条链表的结尾)
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                // next用于记录 拆分完两个链表的结束位置
                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    // 组和组之间的链表断开
                    curr.next = null;
                }

                // 合并两条有序链表
                ListNode merged = merge(head1, head2);

                // prev.next 指向排好序链表的头, 把断开的链表再连接起来
                prev.next = merged;
                while (prev.next != null) {
                    // prev移动到已经排好序的链表的最后一个节点
                    prev = prev.next;
                }
                // 遍历指针指向后面一组的开头, 继续下次循环
                curr = next;
            }
        }
        return dummyHead.next;
    }


    /**
     * 合并两个有序链表
     *
     * @param head1
     * @param head2
     * @return
     */
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }

        temp.next = temp1 != null ? temp1 : temp2;
        return dummyHead.next;
    }
}
